
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null) return null;
        //设置哨兵节点间记录头结点位置
        ListNode sentinel=new ListNode(0);
        sentinel.next=head;
        ListNode lastedSort=head;
        ListNode cur=lastedSort.next;
        while (cur!=null){
            if(cur.val>=lastedSort.val){
                //不用排序了 直接将已排序区域向后移一个
               lastedSort=lastedSort.next;
            }else{
                ListNode pre=sentinel;
                while (pre.next.val<=cur.val){
                    pre=pre.next;
                }
                lastedSort.next=cur.next;
                cur.next=pre.next;
                pre.next=cur;
            }
            cur=lastedSort.next;
        }
        return sentinel.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)































































































































































































